The present invention relates generally to a method and apparatus for carrying out a negotiation using graphs, and more particularly, a method for encapsulating a constraint solver in the negotiation system.
Generally, negotiation has been used for the coordination of autonomous components in distributed applications. A negotiation may be defined as a transaction involving several components, the goal of which is to have the distributed components: (i) agree on a set of actions to be executed by each of them (i.e., reach a consensus on negotiated issues); and (ii) execute the set of actions in an atomic way. There exist different generic models that specify and organize the interactions among the components involved in a negotiation process (e.g., contract nets, auctions with their many variants, bi-lateral negotiations, etc.).
There also exist different mechanisms which address the issue of making informed decisions relevant to a negotiation from the point of view of the individual components that participate in a negotiation. The purpose of these decisions is primarily to make sure that the negotiation remains within the limits of a space of “authorized” solutions (the exact meaning of which is determined by the component making the decisions), and possibly also to orient the negotiation, within that space, towards some “optimal” solutions (again, in the sense of the component making the decisions).
Constraint solvers have been used to delimit the space of solutions authorized by a component in a negotiation. Generally, constraint may be used to express problems in a declarative way. Constraint solvers are generic tools capable of detecting constraint violations, but also inferring new constraints from existing ones. In particular, finite-domain constraints have been used in “constraint logic programming” research, and have also led to commercial implementations such as ILOG and Cosytech.
In addition, mechanisms for performing finite domain constraint solving have been investigated in the field of artificial intelligence (see for example publications, incorporated herein by reference, by: Montanari, entitled “Networks of constraints: Fundamental properties and applications to picture processing”, published in Information Science, volume 7, pages 95-132 1974; and Mackworth, entitled “Constraint satisfaction” published in S. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 285-293, John Wiley & Sons, 1992).
Path-consistency techniques (used for finite domain constraint solving) and in particular arc-consistency techniques (where paths are only considered at length one), have been optimized in many ways (see for example the publication, incorporated herein by reference, by Chen, “Arc consistency revisited”, published in Information Processing Letters, 70:175-184, 1999). Distributed versions of such consistency techniques, for so-called Distributed Constraint Satisfaction Problems (DCSP), have also been developed. In a DCSP, the variables and constraints are distributed among multiple agents, which then have to cooperate to find solutions (see for example the publication, incorporated herein by reference, by Yokoo et al., entitled “Algorithms for distributed constraint satisfaction: A review”, published in Autonomous Agents and Multi-Agent Systems, 3(2): 185-207, 2000).
More generally, the cooperation between multiple, possibly heterogeneous, constraint solvers has also been investigated (see for example the publication, incorporated herein by reference, by Nelson et al., “Simplification by cooperating decision procedures”, published in ACM Transactions on Programming Languages and Systems, 1(2):245-257, 1979, and the publication, incorporated herein by reference, by Shostak “A practical decision procedure for arithmetic with function symbols”, published in Journal of the ACM, 26(2):351-360, 1979).
The basis for the cooperation between constraint solvers generally involves exchanging information linked to shared variables. This mechanism has been generalized and incorporated into generic agent argumentation systems typically for distributed problem solving (see for example the publications, incorporated herein by reference, by: Jung et al., “Argumentation as distributed constraint satisfaction: applications and results”, published in Proceedings of International Conference on Autonomous Agents, pages 324-331, Montreal, QB, Canada, 2001; and Sierra et al., “A framework for argumentation-based negotiation”, published in Singh et al., editors, Intelligent Agents IV: Agent Theories, Architectures, and Languages, volume 1365 of Lecture Notes in Computer Science, pages 177-192. Springer Verlag, 1998).
While constraint solvers are useful, generic tools capable of automating some of the processes taking place in negotiation based applications, their integration in such applications requires some form of encapsulation to turn them into effective negotiators capable of fully taking part in a negotiation process. Constraint solvers have been used to delimit the space of solutions by a component in a negotiation in a prescriptive way by specifying the situations which are not authorized (i.e., those which violate some of the constraints).
Accordingly, it would be desirable to provide a method, and system therefor, for encapsulating arbitrary constraint solvers in negotiation processes that may possibly involve other components which may or may not be constraint aware. Such a method would advantageously involve other components in a negotiation process which are also capable of making negotiation decisions but are not necessarily constraint solvers themselves, nor even constraint aware (e.g., user interfaces for capturing human decisions, ad-hoc components for computing bids in an auction context, data repositories, activity managers, etc.).
In accordance with the embodiments disclosed herein there is provided a method, system and article of manufacture therefor, for encapsulating constraint solvers in graph-based negotiation processes. The method generalizes the constraint propagation mechanism itself, which represents argumentation, and the non-deterministic exploration of alternatives which usually complements constraint propagation in problem solving. This allows the coordination of constraint solvers with other components which may not be constraint solvers at all, nor even constraint aware, and are capable of making non-deterministic (i.e., automatic or human controlled) decisions and sharing them with the participants concerned in the negotiation.
In accordance with one aspect of the embodiments disclosed herein, a class of components is capable of taking part in coordinated negotiations in which graphs are constructed to carry out the negotiations. Decision-makers of the class of components are automated, and their role is to ensure that constraints, normally set by a coordinator of a negotiation, are respected throughout the execution of the negotiation process. The class of components is derived from constraint solvers working by propagation on finite domains. Advantageously, the class of components is adapted to prevent negotiations taking inconsistent paths as well as expose all consequences that may be inferred from each negotiation decision.
In accordance with another aspect of the embodiments disclosed herein, there is provided a system having a processor for carrying out a negotiation concerning a set of actions to be performed by selected ones of a plurality of participants. The system, method and article of manufacture therefor, carry out the negotiation with at least one of the plurality of participants encapsulating a constraint solver in a service. The method defines processing instructions in a memory of the system for carrying out the negotiation using the service encapsulating the constraint solver, and executes the processing instructions with the processor. The processor in executing the processing instructions for carrying out the negotiation with the service encapsulating the constraint solver: (A) establishing encapsulation input in the memory: (a) a mapping between aspects of parameters of the service and corresponding variables of the constraint solver, (b) a translation between negotiation statements on the aspects of the parameters of the service and domain constraints imposed on the corresponding variables of the constraint solver, and (c) a set of semantic constraints of the service on variables of the constraint solver; (B) constructing a graph in the memory for negotiating the set of actions to be performed; each node of the graph defining a negotiation context that has associated therewith a constraint store with at least a set of domain constraints stored therein; (C) propagating constraints defined by the set of semantic constraints and the set of domain constraints associated with nodes of the graph to other participants in the negotiation as domain constraints augment (i.e., further limit the solution space of) the set of semantic constraints during the negotiation.